package first.niuke.midding;

/**
 * @ClassName NC92
 * @description:
 * @author: 荣燊
 * @create: 2021-06-26 13:28
 **/
public class NC92 {
    // 注意最长公共子序列和最长公共子串不是一回事
    public static void main(String[] args) {
        // 输入"1A2C3D4B56","B1D23A456A"。输出"123456"
        LCS( "357486782","13456778"); //输出34678
    }

    /**
     * 思路：https://blog.csdn.net/hrn1216/article/details/51534607
     * dp[i][j]:表示s1以i位结尾，s2以j位结尾时的最长公共子序列
     *   1. s1[i]==s2[j],dp[i][j] = dp[i-1][j-1]+1
     *   2. s1[i]!=s2[j],dp[i][j] = max(dp[i][j-1], dp[i-1][j])
     */
    // 最长公共子序列，注意最长公共子序列和最长公共子串不是一回事
    public static String LCS (String s1, String s2) {
        // write code here
        int len1 = s1.length(); //列数
        int len2 = s2.length(); //行数

        int[][] dp = new int[len2+1][len1+1];

        // 注意行列的顺序，从行开始
        for (int i=1; i<len2+1; i++) { //行
            for (int j=1; j<len1+1; j++) { //列
                if (s1.charAt(j-1) == s2.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        // dp[len2][len1]保存的就是最大的公共子序列的长度
        // 打印dp数组看下
        System.out.print("  ");
        //先将所有的列打印出来。二元数组的0行和0列没有打印
        for (int i=0; i<len1; i++) {
            System.out.print(s1.charAt(i)+" ");
        }
        System.out.println(" ");
        for (int j=0; j<len2; j++) {
            System.out.print(s2.charAt(j)+" ");
            for (int k=1; k<dp[0].length; k++) {
                System.out.print(dp[j+1][k]+" ");
            }
            System.out.println();
        }

        // 这时再使用倒推法，将最长公共子序列构造出来
        StringBuilder stringBuilder = new StringBuilder();
        int j=len1,i=len2;
        while (i>0 && j>0) {
            if (dp[i][j] > dp[i-1][j-1] && dp[i-1][j] == dp[i][j-1]) {
                stringBuilder.append(s1.charAt(j-1));
                i--;
                j--;
            } else if (dp[i][j-1] > dp[i-1][j]) {
                j--;
            } else {
                i--;
            }
        }
        if(stringBuilder.toString().equals("") || stringBuilder==null) {
            return "-1";
        }
        System.out.println(stringBuilder.reverse().toString());


        return stringBuilder.reverse().toString();
    }

}
